package sort;

/**
 * @author huangxin
 * @date 2020/11/14-10:52
 * 计数排序
 */
public class CountingSort {
    static void countingSort(int[] arr) {
        //正数最大,最小
        int max = 0, min = Integer.MAX_VALUE;
        //负数最大,最小
        int negativeMax = Integer.MIN_VALUE, negativeMin = -1;


        for (int num : arr) {
            if (num < 0) {
                if (num > negativeMax) {
                    negativeMax = num;
                }
                if (num < negativeMin) {
                    negativeMin = num;
                }
            } else {
                if (num > max) {
                    max = num;
                }
                if (num < min) {
                    min = num;
                }
            }
        }

        //正数数组
        int[] countArr = new int[max - min + 1];
        //负数数组
        int[] negativeArr = new int[negativeMax - negativeMin + 1];

        for (int num : arr) {
            if (num < 0) {
                //假设 -3 最小 , -2最大
                // -3 * -1  -2  = 1
                // -2 * -1  -2  = 0
                //取出来时 使用 index*-1 + negativeMin即可
                negativeArr[num * -1 + negativeMin]++;
            } else {
                countArr[num - min]++;
            }
        }

        int index = 0;
        for (int i = 0; i < negativeArr.length; i++) {
            while (negativeArr[i] > 0) {
                arr[index++] = i * -1 + negativeMin;
                negativeArr[i]--;
            }
        }

        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                arr[index++] = i + min;
                countArr[i]--;
            }
        }

    }

}
